#pragma once

// 1011. 在 D 天内送达包裹的能力

#include "../Base/CommTool.h"

#include <algorithm>
#include <map>

namespace Solution_1011
{
    class Solution
    {
    public:
        /*
        int shipWithinDays(vector<int> &weights, int days)
        {
            int referenceNum = std::accumulate(weights.begin(), weights.end(), 0); //求和
            int mid = (referenceNum + days - 1) / days;                            //从最小的可能数，开始穷举
            auto highest = std::max_element(weights.begin(), weights.end());
            int start = std::max(mid, *highest);

            //这属于穷举法
            for (int i = start;; ++i)
            {
                if (Check(weights, days, i))
                {
                    return i;
                }
            }

            return 0;
        }
        */
        //二分法思想：
        //上面穷举法中已经列出了最小装载的可能，再算出最大装载的可能，然后进行二分法就可以
        //官方解答如下：
        int shipWithinDays(vector<int> &weights, int days)
        {
            //确定二分查找左右边界
            int left = *std::max_element(weights.begin(), weights.end()); //最小重量

            int right = accumulate(weights.begin(), weights.end(), 0); //最大重量

            while (left < right)
            {
                int mid = (left + right) / 2;
                //need 需要运送的天数
                //curr 当前这一天已经运送的包裹之和
                int need = 1, curr = 0;

                for(int weight : weights)
                {
                    if(curr + weight > mid)
                    {
                        ++need;
                        curr = 0;
                    }
                    curr += weight;
                }
                if(need <= days){ //定位左半段
                    right = mid;
                }
                else{   //定位右半段
                    left = mid + 1;
                }
            }
            return left;
        }

        bool Check(vector<int> &weights, int days, int limitWeight)
        {
            int weightCount = 0;
            int calcDays = 1;
            for (int currWeight : weights)
            {
                if (weightCount + currWeight <= limitWeight)
                {
                    weightCount += currWeight;
                }
                else
                {
                    ++calcDays;
                    if (calcDays > days)
                    {
                        return false;
                    }
                    weightCount = currWeight;
                }
            }
            return true;
        }
    };

    void Test()
    {
        Solution solve;
        std::vector<int> weights{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int days = 5;
        // cout << solve.shipWithinDays(weights, days) << endl;

        weights = {1, 2, 3, 1, 1};
        days = 4;
        cout << solve.shipWithinDays(weights, days) << endl;
    }
}